//1.默认排序
class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        
        unordered_map<int,int> hashmap;
        for(auto&e: nums) {
            hashmap[e]++;
        }

        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> min_q;

        for(auto&[num,count]: hashmap) {
            min_q.push({count, num});  // 小堆的排序方式：默认先从第一个比较，第一个参数是频数，第二个参数是当前数字，反着存储
            if(min_q.size() > k) min_q.pop();
        }
        vector<int> ret;
        while(!min_q.empty()) {
            ret.push_back(min_q.top().second);
            min_q.pop();
        }

        return ret;
    }
};
//2.自定义cmp函数
class Solution {
public:

    static bool cmp(const pair<int, int>& m, const pair<int, int>& n) { //不要this指针
        return m.second > n.second;
    }


    vector<int> topKFrequent(vector<int>& nums, int k) {
        
        unordered_map<int,int> hashmap;
        for(auto&e: nums) {
            hashmap[e]++;
        }
        //用cmp排序
        /*
        priority_queue 的第三个模板参数要求是一个类型，比如：
        仿函数类型（如 struct cmp { ... }）
        Lambda 表达式的类型（用 decltype(cmp)）
        函数指针类型（如 bool(*)(const pair<int,int>&, const pair<int,int>&)）
        */
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(&cmp)> min_q(cmp); 
        //还有cmp构造函数，必须显式传入函数指针作为构造参数
        
        for(auto&[num,count]: hashmap) {
            min_q.push({num, count});  
            if(min_q.size() > k) min_q.pop();
        }
        vector<int> ret;
        while(!min_q.empty()) {
            ret.push_back(min_q.top().first);
            min_q.pop();
        }

        return ret;
    }
};
//3. On--桶排序
class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> freq;
        for (int num : nums) freq[num]++;

        int n = nums.size();
        vector<vector<int>> buckets(n + 1);  // freq 最大不会超过 n
        for (auto& [num, count] : freq) {
            buckets[count].push_back(num);  //当前频数下有几个元素
        }

        vector<int> res;
        for (int i = n; i >= 0 && res.size() < k; --i) {
            for (int num : buckets[i]) {  //遇见空数组跳过
                res.push_back(num);
                if (res.size() == k) break;
            }
        }
        return res;
    }

};


